public class Solution {
    /*
     * 跳跃游戏
     * 状态：F(i) 能否处于i位置
     * 状态转移方程：j < i
     *           F(i) = F(j) && i-j<=nums[j]
     *           (i-j<=nums[j] 这个条件就锁死了：如果nums[j] == 0; 绝对不可能由j位置到达i位置,因为i-j最小是1)
     * 初始状态：
     *       F(0) = true;
     * */
    public boolean canJump(int[] nums) {
//有没有无所谓了其实。。。
//        int k = 0;
//        for(; k <nums.length-1; k++){
//            if(nums[k] == 0){
//                break;
//            }
//        }
//        if(k==nums.length-1){
//            return true;
//        }

        int len = nums.length;
        boolean[] canArr = new boolean[len];
        canArr[0] = true;
        for (int i = 1; i < len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                canArr[i] = canArr[j] && i - j <= nums[j];
                if (canArr[i]) {
                    break;
                }
            }
        }
        return canArr[len - 1];
    }


    /*
     * 状态：F(i)跳到i位置所需要的次数
     * 状态转移方程：
     *           j = 0; j < i; j++
     *          (除了0位置,F(j) != 0)并且(i-j<nums[j])    F(i) = min(F(j) + 1)
     *          不能到达 F(i) = 0;
     * 初始状态：
     *         F(0) = 0;
     * 返回结果：
     *        F(len-1)
     * */
    public int jump(int[] nums) {
        int len = nums.length;
        int[] Jump = new int[len];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (i - j <= nums[j] && (nums[j] != 0 || j == 0)) {
                    if (Jump[i] == 0) {
                        Jump[i] = Jump[j] + 1;
                    } else {
                        Jump[i] = Math.min(Jump[i], Jump[j] + 1);
                    }
                }
            }
        }
        return Jump[len - 1];
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(13));
    }
}
